Nowadays, Electronic Design Automation (EDA) tools are challenged by design goals at the frontier of what is achievable in advanced technologies. In this scenario, recent logic synthesis works considered (slower) Boolean methods [1]-[5] rather than (faster) algebraic methods [6]-[9] to obtain superior circuit realizations, in terms of speed, power and area. Indeed, it is desirable to spend more time in logic synthesis computation to get a better final design. However, with traditional tools, there is a limit after which spending more effort in logic synthesis, for example running complex Boolean methods, does not improve a circuit quality or even requires too long runtime [10]. To push this limit as far as possible, innovative data structures and manipulation laws are decisive.
Majority-Inverter Graph (MIG) is a promising data structure for logic optimization and synthesis recently introduced by [11]. An MIG is a directed acyclic graph consisting of three-input majority nodes and regular/complemented edges. MIG manipulation is supported by a consistent algebraic framework. Algebraic optimization of MIGs showed strong synthesis results. However, the heuristic and local (short-sighted) nature of MIG algebraic methods [11] might preclude global (far-sighted) optimization opportunities.
In the present application, we extend the capabilities of MIG logic optimization by developing powerful Boolean methods based on majority voting. The present MIG Boolean methods enforce simplification opportunities by inserting logic errors successively masked by MIG nodes. Thanks to the data-structure/methodology fitness, the present MIG Boolean methods have an efficient runtime, i.e., they can handle 100 k equivalent gates in less than a minute, on a standard laptop. The present Boolean methods are simple, yet powerful. Experiments combined with state-of-art MIG algebraic techniques show tremendous results. For example, when targeting depth reduction, the presently described MIG optimizer automatically transforms a ripple carry adder into a carry look-ahead one. Considering the set of IWLS'05 (arithmetic intensive) benchmarks, the present MIG optimizer reduces by 17.98% (26.69%) the logic network depth while also enhancing size and power activity metrics, with respect to ABC tool [13]. Without MIG Boolean methods, using MIG algebraic optimization alone, only (about) half of the aforementioned gains appeared in our experiments. Employed as front-end to a delay-critical 22-nm ASIC flow (logic synthesis+physical design) our MIG optimizer reduces the average delay/area/power by (15.07%, 4.93%, 1.93%), over 27 academic and industrial benchmarks, as compared to a leading commercial ASIC flow.